package com.hutu;

/**
 * 买卖股票的最佳时机
 *
 * @author hutu
 * @date 2020/10/13 4:05 下午
 */
public class MaxProfit {

    /**
     * 121. 买卖股票的最佳时机 （link：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/）
     */
    public static int maxProfit(int[] prices) {
        int length = prices.length;
        int dp_i_0 = 0;
        int dp_i_1 = Integer.MIN_VALUE;
        for (int i = 0; i < length; i++) {
            dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
            dp_i_1 = Math.max(dp_i_1, -prices[i]);
        }
        return dp_i_0;
    }

    /**
     * 122. 买卖股票的最佳时机 II （link：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/）
     */
    public static int maxProfit1(int[] prices) {
        int length = prices.length;
        int dp_i_0 = 0;
        int dp_i_1 = Integer.MIN_VALUE;
        int temp;
        for (int i = 0; i < length; i++) {
            temp = dp_i_0;
            dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
            dp_i_1 = Math.max(dp_i_1, temp - prices[i]);
        }
        return dp_i_0;
    }

    /**
     * 188. 买卖股票的最佳时机 IV （link：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/）
     */
    public static int maxProfit2(int k, int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int length = prices.length;
        // k 大于 length 就相当于无数次
        if (k > length / 2) {
            return maxProfit(prices);
        }
        int[][][] dp = new int[length][k + 1][2];

        for (int i = 0; i <= k; i++) {
            dp[0][i][0] = 0;
            dp[0][i][1] = -prices[0];
        }
        for (int i = 1; i < length; i++) {
            for (int j = k; j > 0; j--) {
                dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
                dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
            }
        }
        return dp[length - 1][k][0];
    }


    public static void main(String[] args) {
        System.out.println(maxProfit(new int[]{7, 1, 5, 3, 6, 4}));
        System.out.println(maxProfit1(new int[]{7, 1, 5, 3, 6, 4}));
        System.out.println(maxProfit2(2,new int[]{3,2,6,5,0,3}));
    }
}
